package leencode;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

public class no146_LRU缓存 {

    @Test
    public void test(){
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        int i = lruCache.get(1);
        System.out.println("get1:" + i);
        lruCache.put(3,3);
        int i2 = lruCache.get(2);
        System.out.println("get2:" + i2);

        lruCache.put(4,4);
        int i1 = lruCache.get(1);
        System.out.println("get1:" + i1);
    }

    @Test
    public void test1(){
        LRUCache lruCache = new LRUCache(1);
        lruCache.put(2,1);
        int i = lruCache.get(2);
        System.out.println("get2:" + i);
        lruCache.put(3,2);
        int i2 = lruCache.get(2);
        System.out.println("get2:" + i2);

        int i1 = lruCache.get(3);
        System.out.println("get3:" + i1);
    }

    @Test
    public void test2(){
        LRUCache lruCache = new LRUCache(2);
        int i = lruCache.get(2);
        System.out.println("get2:" + i);

        lruCache.put(2,6);
        int i1 = lruCache.get(1);
        System.out.println("get1:" + i);

        lruCache.put(1,5);
        lruCache.put(1,2);
        int i2 = lruCache.get(1);
        System.out.println("get1:" + i2);

        int i3 = lruCache.get(2);
        System.out.println("get2:" + i3);
    }

    @Test
    public void test3(){
        LRUCache lruCache = new LRUCache(2);

        lruCache.put(2,1);
        lruCache.put(3,2);

        int i = lruCache.get(3);
        System.out.println("get3:" + i);

        int i1 = lruCache.get(2);
        System.out.println("get2:" + i1);

        lruCache.put(4,3);

        int i2 = lruCache.get(2);
        System.out.println("get2:" + i2);

        int i3 = lruCache.get(3);
        System.out.println("get3:" + i3);

        int i4 = lruCache.get(4);
        System.out.println("get4:" + i4);
    }

    class LRUCache {

        class Node{

            public int cap;

            public int size = 0;

            public int key;

            public Node next;

            public Node pre;

            public Node(int cap){
                this.cap = cap;
            }

            public Node(int key,Node next, Node pre){
                this.key = key;
                this.next = next;
                this.pre = pre;
                next.pre = this;
                this.cap = next.cap;
                if(next != null){
                    this.size = next.size+1;
                } else {
                    this.size++;
                }

            }
        }

        public Node first;

        public HashMap<Integer,Integer> lruCache;

        public LRUCache(int capacity) {
            lruCache = new HashMap();
            first = new Node(capacity);
        }

        public Node getKey(Node first, int key){
            if(first == null) return null;
            if(first.key == key) return first;
            return getKey(first.next, key);
        }

        public int get(int key) {
            Node keyNode = getKey(this.first,key);
            if(keyNode == null) return -1;
            if (keyNode == this.first) return lruCache.get(key) == null ? -1 : (Integer)lruCache.get(key);
            if(keyNode.pre != null) keyNode.pre.next = keyNode.next;
            if(keyNode.next != null) {
                keyNode.next.pre = keyNode.pre;
            }
            keyNode.pre = null;
            keyNode.next = this.first;
            this.first.pre = keyNode;
            keyNode.size = this.first.size;
            this.first = keyNode;
            return lruCache.get(key) == null ? -1 : (Integer)lruCache.get(key);
        }

        public void put(int key, int value) {
            if (this.first.size == 0) {
                this.first.key = key;
                this.first.size++;
                lruCache.put(key,value);
                return;
            }

            // 已存在key，原node移动到最前方，不创建新的
            if (lruCache.get(key) != null) {
                Node keyNode = getKey(this.first,key);
                if(keyNode.pre != null) keyNode.pre.next = keyNode.next;
                if(keyNode.next != null) keyNode.next.pre = keyNode.pre;
                if (keyNode == this.first) {
                    lruCache.put(key,value);
                    return;
                }
                keyNode.pre = null;
                keyNode.next = this.first;
                this.first.pre = keyNode;
                keyNode.size = this.first.size;
                this.first = keyNode;
            } else {
                Node newFirst = new Node(key, first, null);
                this.first = newFirst;
                if (first.size > first.cap){
                    Node foot = getFootKey(this.first);
                    lruCache.remove(foot.key);
                    if(foot.pre != null){
                        foot.pre.next = null;
                    }
                    this.first.size = this.first.size-1;
                }
            }
            lruCache.put(key,value);
        }

        public Node getFootKey(Node first){
            if (first == null) return null;
            if (first.next == null) return first;
            return getFootKey(first.next);
        }
    }





}
